闲话
C好难,D好水.本场链接:Codeforces Round #592
A. Pens and Pencils
题目大意:一根钢笔可以写篇文章,一根铅笔可以画张画,最多只能带支笔.要写篇文章,画幅画.问是否可以完成,如果可以,输出带的钢笔和铅笔的数量.
数据范围:
思路
至少要有上取整的根钢笔和上取整的根铅笔,加起来不到就满足.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
int l = ceil(double(a) / c);
int r = ceil(double(b) / d);
if(l + r > k) puts("-1");
else printf("%d %d\n",l,r);
}
return 0;
}
B. Rooms and Staircases
原题大意:有一个的棋盘,棋盘上下不是全部相连的,上下的相连关系由一个字符串给出,如果说明第位上下的格子是联通的.现在有一个机器人,你可以任意指定他的初始位置,并且不能经过之前已经经过的边,问你最多能走过多少个格子.
数据范围:
错解思路
显然如果能转向就转向,这个时候每一个都可以给我提供个的步数,如果不能转向,那就是的贡献.直接扫描统计字符串即可.错了的原因是,初始位置是不固定的,而且不能简单地就这样统计的步数,如果另一边可以绕一圈过来,就可能导致字符串位置上虽然是,但是实际这一列的贡献是的情况.
正解思路
很显然,如果我转向了一次,之后是可以再转回来的,如果我从最左端出发,那么走到一个最远的之后绕一圈,这样的距离步数是最大的.于是可以统计最左端和最右端的的位置,分别乘表示我绕了一圈,统计答案即可.如果没有那就只能走一条直线,答案为.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
char s[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
scanf("%s",s + 1);getchar();
int res = 0,L = 0x3f3f3f3f,R = -1;
for(int i = 1;i <= n;++i)
{
if(s[i] == '1')
L = min(L,i),R = max(R,i);
}
if(R == -1)
{
printf("%d\n",n);
continue;
}
res = max({res,L * 2,(n - L + 1) * 2});
res = max({res,R * 2,(n - R + 1) * 2});
printf("%d\n",res);
}
return 0;
}
C. The Football Season
题目大意:解不定方程:
其中是未知数,其余已知.
求出一组解即可.
数据范围:
错解思路
这题要的就是找一个最小的解,因为越小留给的空间就越大,如果最小值都比大则无解,那求不定方程,直接上.错就错在数据范围太大了,如果直接显然会导致爆long long.
正解思路
想要知道怎么找的最小的解的,一是消元,二是可以从方程入手:
不定方程本身是没什么信息的,可以想办法等价变形,找出各个解的形式:
原式
故不定方程的解都满足以及的形式.因为,所以减小的速度比增大的速度快,进而如果达到最小,那么也就达到了最小.而所有的满足这个形式,所以最终答案的最小的的取值范围就是.这一点是比较好想的,又注意到所以可以直接枚举的取值,如果合法就直接输出,全部都不合法就说明无解,因为最小的都不够用,就不可能有更好的情况了.另外有一个博客也是讲这个问题,推荐一下:关于ax+by=c的解x,y的min(|x|+|y|)值问题
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,p,w,d;cin >> n >> p >> w >> d;
ll sres = 0,resx = -1,resy = -1;
for(ll y = 0;y < w;++y)
{
ll A = p - d * y;
if(A % w == 0)
{
ll x = A / w;
if(x >= 0 && x + y <= n)
{
cout << x << " " << y << " " << n - x - y << endl;
return 0;
}
}
}
cout << "-1";
return 0;
}
D. Paint the Tree
题目大意:有一个点的无根树,给定每个节点染成某种颜色的代价.颜色只有三种,要求树上三个相连的节点颜色是不能相同的.求是否能染色这棵树,如果能,求出最小代价.
数据范围:
思路
首先考虑什么时候无解:对于某一个点来说,如果与他相连的点达到个或以上,就无解.这一点应该是很显然的,因为一旦连了个点必然会导致颜色相同,因此整颗树上不存在一个度数为的点.这就意味着:这棵树退化成了一个链.这是一个非常强的条件.找到了这个条件之后整个题就变得简单了:因为对于一个链来说,如果他的首/尾和与之相连的颜色确定了,那么整个链的颜色也就确定了.
首先找到一个度数为的点,标记成根节点.枚举根节点和与之相邻的点的颜色,然后直接确定整个链的代价.并记录代价和具体方案,统计一下即可.
注意权值很大,会爆int.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
int cost[3][N],deg[N],n,col[N],rescol[N];
vector<int> edges[N];
ll res;
void dfs(int u,int fa,int c1,int c2)
{
for(auto& v : edges[u])
{
if(v == fa) continue;
int c = 3 - c1 - c2;
res += cost[c][v];
col[v] = c;
dfs(v,u,c2,c);
}
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < 3;++i)
for(int j = 1;j <= n;++j)
scanf("%d",&cost[i][j]);
int root = 1,ok = 1;
for(int i = 1;i < n;++i)
{
int u,v;scanf("%d%d",&u,&v);
edges[u].push_back(v);++deg[u];
edges[v].push_back(u);++deg[v];
}
for(int i = 1;i <= n;++i)
{
if(deg[i] >= 3)
{
ok = 0;
break;
}
else if(deg[i] == 1) root = i;
}
if(!ok) puts("-1");
else
{
ll reres = 0x3f3f3f3f3f3f3f3f;
for(int i = 0;i < 3;++i)
{
for(int j = 0;j < 3;++j)
{
if(j == i) continue;
res = cost[i][root] + cost[j][edges[root].back()];
col[root] = i;col[edges[root].back()] = j;
// cout << res << "*";
dfs(edges[root].back(),root,i,j);
// cout << i << " " << j << " " << res << endl;
if(reres > res)
{
reres = res;
for(int i = 1;i <= n;++i) rescol[i] = col[i];
}
}
}
printf("%lld\n",reres);
for(int i = 1;i <= n;++i) printf("%d ",rescol[i] + 1);
}
return 0;
}
E. Minimizing Difference
题目大意:给定一个长度为的序列,定义diff值为最大值和最小值的差值.你可以给序列里的任意一个元素加一或减一最多次,问最小的diff值是多少.
数据范围:
思路
一开始应该能想到大概贪心直接构造是不行的,但是可以二分答案判断是否是答案.不过这个题就难在怎么写框架上了.
如果答案是的话,说明序列里所有的数都应该这个区间,那么这个区间的取值有个特点,或者这两个数之间一定有一个数是里的值,因为如果两者都不是的话,等价的减少到序列里的值,可以使答案减小,因此一定是有一个的.于是就是在做两种分支:一种是以当前的作为另一种是以当前的作为进行判断.
假如整个序列里最后一个比小的元素是,第一个比大的元素是.那么修改次数就是左边和右边的部分加起来就行了.即修改次数,求和部分可以前缀和.
最后考虑怎么找和.首先对于是的情况,要找的就是一个的最大的之后的一位(额外加一位,使得).其次对于是的情况,要找的就是一个的最小的一位.注意对于这两种情况而言,对应的或不一定是.比如前者的实际上是,后者的实际上是.最后看答案是不是合法的就行了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
ll n,k,a[N],s[N];
bool check(int x)
{
for(int i = 1,j = 1;i <= n;++i)
{
while(j <= n && a[j] - a[i] <= x) ++j;
if(a[i] * (i - 1) - s[i - 1] + s[n] - s[j - 1] - (a[i] + x) * (n - j + 1) <= k) return 1;
}
for(int i = 1,j = 1;i <= n;++i)
{
while(a[i] - a[j] > x) ++j;
if((a[i] - x) * (j - 1) - s[j - 1] + s[n] - s[i] - a[i] * (n - i) <= k) return 1;
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1;i <= n;++i) cin >> a[i];
sort(a + 1,a + 1 + n);
for(int i = 1;i <= n;++i) s[i] = s[i - 1] + a[i];
int l = 0,r = a[n],res;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d",l);
return 0;
}